package 栈和队列;

import java.util.*;

public class LC_347前K个高频元素 {

    public static void main(String[] args){
        int[] nums={1,1,1,2,2,3};
        int k=2;
        System.out.println(Arrays.toString(topKFrequent(nums,k)));
    }
    public static int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int num:nums){
            if(map.containsKey(num))
                map.put(num,map.get(num)+1);
            else
                map.put(num,1);
        }
        PriorityQueue<Integer> pq=new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return map.get(o1)-map.get(o2);
            }
        });
        for(int num:map.keySet()){
            if(pq.size()<k){
                pq.add(num);
            }
            else if(map.get(num)>map.get(pq.peek())){
                pq.remove();
                pq.add(num);
            }
        }
//        List<Integer> list=new ArrayList<>();
//        while(!pq.isEmpty())
//            list.add(pq.remove());
        int[] res=new int[k];
        for(int i=0;i<k;i++){
            res[i]=pq.remove();
        }
        return res;
    }
}
